The present invention relates to a method of determining the intersection of two polygons, particularly with respect to determining the intersection of two polygons that represent geographic features.
In geographic databases, polygons are used to represent two-dimensional areas, such as lakes, recreational parks, cities, counties, states, golf courses, and so on. A commonly needed function performed using a geographic database is to find that part of one two-dimensional geographic feature (such as a lake, a recreational park, etc.) which is located inside another two-dimensional geographic feature (such as a city, county, state, and so on). The solution can be found by determining the intersection of the polygons used to represent the two-dimensional geographic features.
There are prior methods for determining the intersection of polygons. One well known algorithm for determining the intersection of polygons is described in Computational Geometry (O'Rourke, Joseph. Second Edition. Cambridge University Press, 1998). This algorithm takes all shape points from two polygons, sorts them by their y coordinate value and sweep searches the line segments at each shape point from top to bottom. If a line segment is located in both polygons, then it is an intersection boundary. With this prior algorithm, if there are n shape points in two polygons, the overall complexity is n*log(n). Thus, although this prior algorithm works satisfactorily, it is computationally intensive and accordingly takes a relatively large amount of time to obtain a result.
Therefore, there is a need for faster way to determine the intersection of two polygons.